POI2013 Watering can

POI
BIT, 线段树

POI2013 Watering can

题目大意：

$PS.$罕见的数据结构题！！！

有三类操作：

  1. void inicjuj(int n, int k, int *D)；

    只在开头出现一次，给出序列的长度，一个指标k，以及维护的序列D。

  2. void podlej(int a, int b)；

    把D数组区间[a,b]都加1。

  3. int dojrzale(int a, int b)；

    询问区间[a,b]之间大于等于k的数有几个。

题解：

我们用一个线段树来维护原有的序列，用一个bit维护已经大于等于k的数的序列。每进行一次操作二，就对[a,b]求最大值，若最大值大于等于k，说明这个数一直对答案有贡献，那么我们把线段树上的该点去掉(改成-inf，这样就不会被多次算到了)，并加入到bit中。询问时，直接在bit上区间询问即可。

由于每一个数只会被塞入bit一次，因而复杂度为$O((n+m)logn)$.

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
#include<string.h>
#include<algorithm>
#include<iostream>
using namespace std;
const int N=300001,inf=(int)1e9;
int K,num[N];
struct BIT{
	#define lowbit(x) (x&(-x))
	int bit[N];
	BIT(){
		memset(bit,0,sizeof(bit));
	}
	void add(int x){
		for(;x<N;x+=lowbit(x))bit[x]++;
	}
	int sum(int x){
		int res=0;
		for(;x;x-=lowbit(x))res+=bit[x];
		return res;
	}
	int query(int L,int R){
		return sum(R)-sum(L-1);
	}
}T;
struct node{
	int L,R,mx,id,add;
}tree[N<<2];
struct Segment_Tree{
	void up(int p){
		if(tree[p<<1].mx>tree[p<<1|1].mx)tree[p].mx=tree[p<<1].mx,tree[p].id=tree[p<<1].id;
		else tree[p].mx=tree[p<<1|1].mx,tree[p].id=tree[p<<1|1].id;
	}
	void down(int p){
		if(tree[p].add){
			tree[p<<1].mx+=tree[p].add;
			tree[p<<1|1].mx+=tree[p].add;
			tree[p<<1].add+=tree[p].add;
			tree[p<<1|1].add+=tree[p].add;
			tree[p].add=0;
		}
	}
	void build(int L,int R,int p){
		tree[p].L=L,tree[p].R=R,tree[p].add=0;
		if(L==R){
			tree[p].mx=num[L-1],tree[p].id=L-1;
			return;
		}
		int mid=L+R>>1;
		build(L,mid,p<<1);
		build(mid+1,R,p<<1|1);
		up(p);
	}
	void update(int L,int R,int p){
		if(tree[p].L==L&&tree[p].R==R){
			tree[p].mx++;
			tree[p].add++;
			return;
		}
		down(p);
		int mid=tree[p].L+tree[p].R>>1;
		if(R<=mid)update(L,R,p<<1);
		else if(L>mid)update(L,R,p<<1|1);
		else update(L,mid,p<<1),update(mid+1,R,p<<1|1);
		up(p);
	}
	void remove(int x,int p){
		if(tree[p].L==tree[p].R){
			tree[p].mx=-inf;
			return;
		}
		down(p);
		int mid=tree[p].L+tree[p].R>>1;
		if(x<=mid)remove(x,p<<1);
		else remove(x,p<<1|1);
		up(p);
	}
	node query(int L,int R,int p){
		if(tree[p].L==L&&tree[p].R==R)return tree[p];
		down(p);
		int mid=tree[p].L+tree[p].R>>1;
		if(R<=mid)return query(L,R,p<<1);
		else if(L>mid)return query(L,R,p<<1|1);
		else{
			node Lson=query(L,mid,p<<1),Rson=query(mid+1,R,p<<1|1);
			if(Lson.mx>Rson.mx)return Lson;
			return Rson;
		}
	}
}ST;
void inicjuj(int n, int k, int *D){
	K=k;
	for(int i=0;i<n;i++){
		num[i]=D[i];
		if(num[i]>=K){
			num[i]=-inf;
			T.add(i+1);
		}
	}
	ST.build(1,n,1);
}
void podlej(int a, int b){
	ST.update(a+1,b+1,1);
	while(true){
		node cur=ST.query(a+1,b+1,1);
		if(cur.mx>=K){
			ST.remove(cur.id+1,1);
			T.add(cur.id+1);
		}else break;
	}
}
int dojrzale(int a, int b){
	return T.query(a+1,b+1);
}
分享到 评论